Partial Permutation
   HOME

TheInfoList



OR:

In
combinatorial mathematics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...
, a partial permutation, or sequence without repetition, on a
finite set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. Th ...
''S'' is a
bijection In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
between two specified
subset In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
s of ''S''. That is, it is defined by two subsets ''U'' and ''V'' of equal size, and a
one-to-one mapping In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositi ...
from ''U'' to ''V''. Equivalently, it is a
partial function In mathematics, a partial function from a set to a set is a function from a subset of (possibly itself) to . The subset , that is, the domain of viewed as a function, is called the domain of definition of . If equals , that is, if is de ...
on ''S'' that can be extended to a
permutation In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...
.


Representation

It is common to consider the case when the set ''S'' is simply the set of the first ''n'' integers. In this case, a partial permutation may be represented by a string of ''n'' symbols, some of which are distinct numbers in the range from 1 to n and the remaining ones of which are a special "hole" symbol ◊. In this formulation, the
domain Domain may refer to: Mathematics *Domain of a function, the set of input values for which the (total) function is defined **Domain of definition of a partial function **Natural domain of a partial function **Domain of holomorphy of a function * Do ...
''U'' of the partial permutation consists of the positions in the string that do not contain a hole, and each such position is mapped to the number in that position. For instance, the string "1 ◊ 2" would represent the partial permutation that maps 1 to itself and maps 3 to 2.. The seven partial permutations on two items are :◊◊, ◊1, ◊2, 1◊, 2◊, 12, 21.


Combinatorial enumeration

The number of partial permutations on ''n'' items, for ''n'' = 0, 1, 2, ..., is given by the
integer sequence In mathematics, an integer sequence is a sequence (i.e., an ordered list) of integers. An integer sequence may be specified ''explicitly'' by giving a formula for its ''n''th term, or ''implicitly'' by giving a relationship between its terms. For ...
:1, 2, 7, 34, 209, 1546, 13327, 130922, 1441729, 17572114, 234662231, ... where the ''n''th item in the sequence is given by the summation formula :\sum_^n i!\binom^2 in which the ''i''th term counts the number of partial permutations with support of size ''i'', that is, the number of partial permutations with ''i'' non-hole entries. Alternatively, it can be computed by a
recurrence relation In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
:P(n) = 2nP(n-1) - (n-1)^2 P(n-2). This is determined as follows: #P(n-1) partial permutations where the final elements of each set are omitted: #P(n-1) partial permutations where the final elements of each set map to each other. #(n-1)P(n-1) partial permutations where the final element of the first set is included, but does not map to the final element of the second set #(n-1)P(n-1) partial permutations where the final element of the second set is included, but does not map to the final element of the first set #-(n-1)^2P(n-2), the partial permutations included in both counts 3 and 4, those permutations where the final elements of both sets are included, but do not map to each other.


Restricted partial permutations

Some authors restrict partial permutations so that either the domain. or the range of the bijection is forced to consist of the first ''k'' items in the set of ''n'' items being permuted, for some ''k''. In the former case, a partial permutation of length ''k'' from an ''n''-set is just a sequence of ''k'' terms from the ''n''-set without repetition. (In elementary combinatorics, these objects are sometimes confusingly called " ''k''-permutations" of the ''n''-set.)


References

{{reflist Combinatorics Functions and mappings